package algocasts;

import java.util.*;

public class P131_PathSumII {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    private void path(TreeNode root, int sum,
                      List<Integer> elem, List<List<Integer>> res) {
        if (root == null) return;
        elem.add(root.val);
        if (root.left == null && root.right == null && root.val == sum)
            res.add(new ArrayList<>(elem));
        path(root.left, sum - root.val, elem, res);
        path(root.right, sum - root.val, elem, res);
        elem.remove(elem.size() - 1);
    }

    // Time: O(n)  Space: O(n)
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> elem = new ArrayList<>();
        path(root, targetSum, elem, res);
        return res;
    }

    public List<List<Integer>> pathSum_Iterative(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> elem = new ArrayList<>();

        Stack<TreeNode> stack = new Stack<>();
        Set<TreeNode> visited = new HashSet<>();
        int curSum = 0;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                elem.add(root.val);
                curSum += root.val;
                visited.add(root);
                stack.push(root);
                root = root.left;
            }
            TreeNode n = stack.peek();
            if (n.right == null || visited.contains(n.right)) {
                if (n.left == null && n.right == null && curSum == targetSum)
                    res.add(new ArrayList<>(elem));
                stack.pop();
                elem.remove(elem.size() - 1);
                curSum -= n.val;
                root = null;
            } else root = n.right;
        }
        return res;
    }


}
